//
//  Trie.cpp
//  DemoV2
//
//  Created by 董一龙 on 2022/8/6.
//

#include "Trie.hpp"

Trie::Trie() : root(new Trie::Node) {}
Trie::~Trie() {
    if(root) {
        for(auto charAndNode : root->subNodeMap) {
            Trie::Node *node;
            std::tie(std::ignore, node) = charAndNode;
            delete node;
            node = nullptr;
        }
        delete root;
        root = nullptr;
    }
}

/// 向可匹配的前缀集添加前缀
/// @param prefixPattern 要添加的前缀，例如"abc*"
/// 默认星号在结尾，不支持星号在中间，没有转义。
/// 空字符串无效，支持*，意为匹配任何字符串
void Trie::insertPrefix(std::string const& prefixPattern) {
    if(prefixPattern.empty()) {
        return;
    }
    
    if(!root) {
        root = new Trie::Node;
    }
    
    Trie::Node *subroot = root;
    
    for (auto ch : prefixPattern) {
        if(subroot &&
           subroot->subNodeMap.find(ch) == subroot->subNodeMap.end()) {
            subroot->subNodeMap[ch] = new Trie::Node;
        }
        subroot = subroot->subNodeMap[ch];
    }
    
    if(prefixPattern.back() != '*' &&
       subroot->subNodeMap.find('*') == subroot->subNodeMap.end()) {
        subroot->subNodeMap['*'] = new Trie::Node;
    }
    
    return;
}

/// 向可匹配的前缀集添加多个前缀
/// @param prefixPatternSet 前缀集合，例如 { "ab*", "ac*", "cd*"}
void Trie::insertPrefixSet(std::initializer_list<std::string> const& prefixPatternSet) {
    for(auto const& prefixPattern : prefixPatternSet) {
        insertPrefix(prefixPattern);
    }
}

/// 可匹配前缀集中存在某个前缀匹配了输入字符串
/// @param str 输入字符串，假设输入字符串没有星号。空字符串返回false
/// @return bool 是否存在前缀匹配
bool Trie::hasPrefixMatch(std::string const& str) const {
    if(!root || str.empty()) {
        return false;
    }
    Trie::Node *subroot = root;
    for(auto ch : str) {
        if(subroot->subNodeMap.find('*') != subroot->subNodeMap.end()) {
            return true;
        }
        if(subroot->subNodeMap.find(ch) == subroot->subNodeMap.end()) {
            return false;
        }
        if(subroot->subNodeMap.find(ch) != subroot->subNodeMap.end()) {
            subroot = subroot->subNodeMap.at(ch);
        }
    }
    // assert(0 && "trie树构建错误，存在不以*结尾的路径");
    return false;
}
